/* Copyright 2012 Tobias Marschall
 *
 * This file is part of CLEVER.
 *
 * CLEVER is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * CLEVER is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with CLEVER.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef OVERLAPPINGREGIONS_H_
#define OVERLAPPINGREGIONS_H_

#include <iostream>
#include <vector>
#include <cassert>

/** A set of (possibly) overlapping intervals. */
class OverlappingRegions {
public:
	typedef struct interval_t {
		int chromosome_id;
		int start;
		int end;
		interval_t(int chromosome_id, int start, int end) : chromosome_id(chromosome_id), start(start), end(end) {}
	} interval_t;
private:
	typedef enum { START = 0, END = 1, START_EXCLUDED = 2, END_EXCLUDED = 3 } event_type_t;
	typedef struct event_t {
		int chromosome_id;
		int pos;
		event_type_t type;
		event_t(int chromosome_id, int pos, event_type_t type) : chromosome_id(chromosome_id), pos(pos), type(type) {}
	} event_t;
	friend std::ostream& operator<<(std::ostream& os, const event_t& e);
	mutable std::vector<event_t> events;
	mutable bool changed;
	mutable std::vector<interval_t> disjoint_intervals;
	typedef struct {
		bool operator()(const event_t& e1, const event_t& e2) {
			if (e1.chromosome_id != e2.chromosome_id) return e1.chromosome_id < e2.chromosome_id;
			if (e1.pos != e2.pos) return e1.pos < e2.pos;
			return e1.type < e2.type;
		}
	} event_comparator_t;
	typedef struct {
		bool operator()(const event_t& e1, const event_t& e2) {
			if (e1.chromosome_id != e2.chromosome_id) return e1.chromosome_id < e2.chromosome_id;
			if (e1.pos != e2.pos) return e1.pos < e2.pos;
			assert((e1.type == START) || (e1.type == END));
			assert((e2.type == START) || (e2.type == END));
			return e1.type > e2.type;
		}
	} event_comparator_endfirst_t;
	friend std::ostream& operator<<(std::ostream&, const std::vector<event_t>&);
public:
	OverlappingRegions();
	virtual ~OverlappingRegions();

	/** Add a new interval. Coordinates are inclusive. */
	void add(int chromosome_id, int start, int end);

	/** Add all intervals of another set of regions. */
	void add(const OverlappingRegions& regions);

	/** Remove all given regions. */
	void subtract(const OverlappingRegions& regions);

	/** Reorganize internal representation to use as few memory as possible. */
	void condense() const;

	/** Returns true if the given inteval overlaps with any of the represented regions. */
	bool overlapsWith(int chromosome_id, int start, int end) const;

	/** Returns a list of disjoint intervals that equals the union of the
	 *  underlying set of intervals. The returned intervals are sorted by
	 *  position. */
	const std::vector<interval_t>& list() const;
};

std::ostream& operator<<(std::ostream&, const OverlappingRegions&);

#endif /* OVERLAPPINGREGIONS_H_ */
